# -*- coding: utf-8 -*-
"""
    Time    : 2020/12/30 9:25 下午
    Author  : Thinkgamer
    File    : add06-快速排序and其他排序.py
    Desc    : 小米面试 / 百度面试 （快速排序）
"""


# 快速排序
def quick_sort(arr, left, right):
	def sort(arr, left, right):
		base = arr[left]
		while left < right:
			# 从右往左寻找一个比 base 小的数
			while arr[right] >= base and left < right:
				right -= 1
			# 把比 base 小 的数 赋值给 base 位置
			arr[left] = arr[right]
			
			# 从左往右找到一个比 base 大的数
			while arr[left] < base and left < right:
				left += 1
			arr[right] = arr[left]
		arr[left] = base
		return left
	
	if left < right:
		mid = sort(arr, left, right)
		quick_sort(arr, left, mid-1)
		quick_sort(arr, mid+1, right)


# 冒泡排序
def maopao_sort():
	arr = [9, 7, 5, 3, 2, 4, 6, 8]
	for i in range(0, len(arr)):
		for j in range(i, len(arr)):
			if arr[i] > arr[j]:
				temp = arr[i]
				arr[i] = arr[j]
				arr[j] = temp
	print("冒泡排序的结果为：{}".format(arr))
	
# 插入排序
def insert_sort():
	arr = [9, 7, 5, 3, 2, 4, 6, 8]
	for i in range(1, len(arr)):
		j = i
		while j > 0:
			if arr[j] < arr[j-1]:
				temp = arr[j]
				arr[j] = arr[j-1]
				arr[j-1] = temp
			j -= 1
	print("插入排序的结果为：{}".format(arr))


# 归并排序
def merge_sort(arr):
	def merge(left, right):
		result = list()
		i = 0
		j = 0
		while i < len(left) and j < len(right):
			if left[i] < right[j]:
				result.append(left[i])
				i += 1
			else:
				result.append(right[j])
				j += 1
		while i < len(left) or j < len(right):
			while i < len(left):
				result.append(left[i])
				i += 1
			while j < len(right):
				result.append(right[j])
				j += 1
		return result
				
	if len(arr) < 2:
		return arr
	mid = len(arr) // 2
	return merge(merge_sort(arr[0:mid]), merge_sort(arr[mid: len(arr)]))


# 快速排序
arr = [9, 7, 5, 3, 2, 4, 6, 8]
quick_sort(arr, 0, len(arr)-1)
print("快速排序的结果为：{}".format(arr))


# 冒泡排序
maopao_sort()
# 插入排序
insert_sort()
# 归并排序
arr = [9, 7, 5, 3, 2, 4, 6, 8]
result = merge_sort(arr)
print("归并排序的结果为：{}".format(result))
